package com.fengye.algorithms.leecode;

/**
 * @Author fengye
 * @Date 2023/4/21 6:09
 **/
public class SearchInRotatedSortedArray33 {
    public static void main(String[] args) {
        System.out.println(new SearchInRotatedSortedArray33().search(new int[]{4,5,6,7,8,1,2,3}, 8));
    }

    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length - 1, mid = 0;
        while (lo <= hi) {
            mid = lo + (hi - lo) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段
            if (nums[mid] >= nums[lo]) {
                // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
                if (target >= nums[lo] && target < nums[mid]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return -1;
    }

    public int search2(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if(left == right) {
                if(nums[mid] != target) {
                    break;
                }
            }
            // 因为局部有序
            // 最小的在 左边
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < nums[right]) {
                if(nums[right] == target) {
                    return right;
                }else if(nums[right] > target && target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
                // 最小的在右边
            } else {
                if(nums[left] == target) {
                    return left;
                }else if(nums[left] < target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}
